package org.arithmetic.tree;

/**
 * Created by LUOLIANG on 2016/9/4.
 * 二叉树的遍历
 */
public class BinaryTree {
    //定义一个根结点
    private Node root;

    public BinaryTree(int[] arr) {
        this.root = null;

        for (int i = 0; i < arr.length; i++) {
            createTree(this.root, arr[i]);
        }
    }

    /**
     * 根据传入的data递归构建树
     */
    public void createTree(Node node, int data) {
        if (root == null) {
            root = new Node(data);
        } else {
            if (data < node.data) {
                if (node.leftChild == null) {
                    node.leftChild = new Node(data);
                } else {
                    createTree(node.leftChild, data);
                }
            } else {
                if (node.rightChild == null) {
                    node.rightChild = new Node(data);
                } else {
                    createTree(node.rightChild, data);
                }
            }
        }
    }

    /**
     * 树的结点内部类
     */
    private static class Node {
        private int data;
        private Node leftChild;
        private Node rightChild;

        public Node(int data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    /**
     * 前序遍历
     * 递归
     *
     * @param node
     */
    public void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }

    /**
     * 中序遍历
     * 递归
     *
     * @param node
     */
    public void inOrder(Node node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.data + " ");
            inOrder(node.rightChild);
        }
    }

    /**
     * 后续遍历
     * 递归
     *
     * @param node
     */
    public void postOrder(Node node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.data + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 76, 35, 22, 16, 48, 90, 46, 9, 40};

        BinaryTree binaryTree = new BinaryTree(arr);

        System.out.print("先序遍历: ");
        binaryTree.preOrder(binaryTree.root);
        System.out.println();
        System.out.print("中序遍历: ");
        binaryTree.inOrder(binaryTree.root);
        System.out.println();
        System.out.print("后序遍历: ");
        binaryTree.postOrder(binaryTree.root);
    }
}
